## 无序表

一种数据项按照相对位置存放的数据集被称为“无序表 unordered list”。例：python 中的列表。

### 无序表的实现（链表方案）

虽然列表数据结构要求保持数据项的前后相对位置，但这种前后位置的保持，并不要求数据项依次存放在连续的存储空间

:::tip
链表实现的最基本元素是节点 Node。  
每个节点至少要包含 2 个信息：数据项本身，以及指向下一个节点的引用信息。  
注意 next 为 None 的意义是没有下一个节点了。
:::

#### 节点的实现 python 版

```python

class Node:
    def __init__(self, initData):
        self.data = initData
        self.next = None

    def getData(self):
        return self.data

    def setData(self, data):
        self.data = data

    def getNext(self):
        return self.next

    def setNext(self, next):
        self.next = next


node = Node(2)
print(node.getData()) # 2
print(node.getNext()) # None
```

#### 无序表的实现 python 版

```python

class Node:
    def __init__(self, initData):
        self.data = initData
        self.next = None

    def getData(self):
        return self.data

    def setData(self, data):
        self.data = data

    def getNext(self):
        return self.next

    def setNext(self, next):
        self.next = next


class UnorderList():
    def __init__(self):
        self.head = None

    # 添加一个数据项到列表中，假设item原先不存在于列表中
    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    #在列表中查找item，返回布尔类型值
    def search(self,item):
        current = self.head
        found = False
        while current!= None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

    # 从列表中移除item，列表被修改，item原先应存在于表中
    def remove(self,item):
        current = self.head
        previous = None
        found = False

        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()

        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

    #返回列表包含了多少数据项
    def size(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count

    # 返回列表是否为空
    def isEmpty(self):
        return self.size() == 0

    #添加一个数据项到表末尾，假设item原先不存在于列表中
    def append(self,item):
        current = self.head
        temp = Node(item)
        count = 0
        while count < self.size()-1:
            current = current.getNext()
            count += 1
        current.setNext(temp)

    #返回数据项在表中的位置
    def index(self,item):
        current = self.head
        find = False
        count = 0
        while not find and current!= None:
            if current.getData() == item:
                find = True
            else:
                current = current.getNext()
                count += 1
        if count == self.size() and not find:
            return False
        return count

    #将数据项插入到位置pos，假设item原先不存在与列表中，同时原列表具有足够多个数据项，能让item占据位置pos
    def insert(self,pos,item):
        current = self.head
        previous = None
        count = 0
        while count < pos:
            previous = current
            current = current.getNext()
            count +=1

        if pos == 0:
            self.add(item)
        else:
            temp = Node(item)
            temp.setNext(current)
            previous.setNext(temp)

    #从列表末尾移除数据项，假设原列表至少有1个数据项
    def pop(self):
        current = self.head
        previous = None
        count = 0
        while count < self.size()-1:
            previous = current
            current = current.getNext()
            count += 1

        if self.size() == 1:
            self.head = None
            return current.getData()
        else:
            previous.setNext(None)
            return current.getData()

    #移除位置为pos的数据项，假设原列表存在位置pos
    def popIndex(self,pos):
        current = self.head
        previous = None
        count = 0
        if pos == 0:
            self.head = current.getNext()
            return current.getData()
        while count < pos and current != None:
            previous = current
            current = current.getNext()
            count += 1
        previous.setNext(current.getNext())
        return current.getData()



list = UnorderList()
list.add('a')
list.append('b')
print(list.size())
print(list.index('b'))
print(list.search('b'))
```

## 有序表

有序表是一种数据项依照其某可比性质（如整数大小、字母表先后）来决定在列表中的位置

### 有序表的实现 (链表方案)

:::tip
下面对数据项的讨论并不仅适用于整数，可适用于所有定义了**gt**方法（即>操作符）的数据类型。
:::
同样采用链表方法实现有序表，Node 定义相同。需要记住的是，数据项的相对位置，取决于它们之间的“大小”比较。
有序表的节点与无序表的一样，并且大部分方法与无序表的方法也一样，只有 search 方法和 add 方法有所不同：

- search 方法：
  对于有序表来说，可以利用链表节点有序排列的特性，来为 search 节省不存在数据项的查找时间。

```python
def search(self,item):
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.get_next()
        return found


```

- add 方法：

相比无序表，有序表添加数据项时，必须保证加入的数据项添加在合适的位置，以维护整个链表的有序性。
以从小到大的顺序为例：需要先找到恰好大于新数据项的数据项，然后将新数据项插入该数据项的前面。

```python
def add(self,item):
    current = self.head
    previous = None
    stop = False
    while current != None and not stop:
        if current.getData() > item:
            stop = True
        else: # 说明还在后面
            previous = current ## 先记录一下当前的节点
            current = current.getNext() ## 跳转到后面一个节点继续比较

    temp = Node(item)
    if previous == None:
        temp.setNext(self.head)
        self.head = temp
    else:
        temp.setNext(current)
        previous.setNext(temp)

```

## 复杂度分析

    - isEmpty是O(1)，因为仅需要检查head是否为None
    - size是O(n)，因为除了遍历到表尾，没有其它办法得知节点的数量
    - search/remove以及有序表的add方法，则是O(n)，因为涉及到链表的遍历，按照概率其平均操作的次数是n/2
    - 无序表的add方法是O(1)，因为仅需要插入到表头
